public class Sort2 {
    public static void shellSort(int[] array) {
        int gap = array.length;
        //当只剩下一组停止,实际上上一次循环已经将gap=1时的数组排序了
        while (gap>1) {
            gap = gap/3+1;
            shell(array,gap);
        }
    }
    //对已经分好组的数组进行插入排序
    private static void shell(int[] array,int gap) {
        //i的起始值不能是1下标，而是gap
        //i不用+gap这样只能对一组元素进行排序,i++直接对gap组元素同时进行排序
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            //j对每组组内元素进行比较，所以j起始值得为i-gap,并且每次j=j-gap
            int j = i-gap;
            for (; j >=0 ; j-=gap) {
                if (array[j]>tmp) {
                    array[j+gap] = array[j];
                } else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
}
